// 给定一个字符串S，检查是否能重新排布其中的字母，使得两相邻的字符不同。
// 若可行，输出任意可行的结果。若不可行，返回空字符串。

// 字符信息结构体
interface StrInfo {
    str: string;
    count: number;
}
// 暴露接口
const reorganizeString = function (S: string) {
    const hashMap = new Map<string, number>();
    // 先利用哈希表来计数
    for (let i = 0; i < S.length; i++) {
        let currValue: number = hashMap.get(S[i]) || 0;
        hashMap.set(S[i], currValue + 1);
    }
    // 对哈希表的频数生成相应的结构体存储，并基于频数升序排序(基于性能考量)
    const strInfoList: StrInfo[] = [];
    hashMap.forEach((value, key) => {
        strInfoList.push({
            str: key,
            count: value
        });
    })
    strInfoList.sort((a, b) => a.count - b.count);
    // 检查是否可以构造成功
    if (strInfoList[strInfoList.length - 1].count >= Math.ceil(S.length / 2) + 1) {
        return '';
    }
    // 如可以构造，对频率排序并构造，
    const strList: string[] = new Array(S.length);
    // 把频率高的先在偶数位置排满
    for (let i = 0; i < S.length; i = i + 2) {
        // 填奇数位字符串
        reorganizeString_fill(strInfoList, strList, i);
    }
    // 继续填偶数位置
    for (let i = 1; i < S.length; i = i + 2) {
        // 填偶数位字符串
        reorganizeString_fill(strInfoList, strList, i);
    }
    return strList.join('');
};

// 辅助函数——填表
function reorganizeString_fill(infoList: StrInfo[], strList: string[], currIndex: number) {
    // 判断当前末尾元素的计数是否大于0
    if (infoList[infoList.length - 1].count === 0) {
        infoList.pop();
    }
    let lastStrInfo: StrInfo = infoList[infoList.length - 1]
    strList[currIndex] = lastStrInfo.str;
    lastStrInfo.count--;
}

reorganizeString("wawwivhwfrgontvvfggh")


// 这道题目算是细节较为繁琐的字符串类型
// 这道题目的思维盲区在于最后的构造结果不光受最大频数字符的影响，同时还受其余字符的影响
// 而谈到频数比较好想到的是首先需要使用哈希表计数
// 而当哈希表的计数完成后，我们可以构造一个结构体对象，抽象出字符和当前频数的集合
// 之后对这个结构体对象进行基于频数升序排序(基于pop的性能考量)
// 然后取出末尾元素（频数最大的字符结构体）检查是否可以构造成功
// 构造成功的要求可以在纸上画一画得到答案
// 然后构造出一个字符数组，然后往字符数组里进行填字符的操作
// 这里的一个重要细节是偶索引和奇索引分开基于频数降序排序来填表操作
// 这样做的好处是既可以保证结构体数组的末尾是最高频数的字符结构体
// 又可以保证两两字符是一定不相邻
// 在填表的过程中也要记得更新结构体和结构体数组
// 之后完成这个字符数组返回即得到最终答案。